package com.sicheng.algorithm.recursive.dfs;

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/11/15 14:34
 */
public class 非单位时间任务安排问题 {


    /**
     * ★问题描述:具有截止时间和误时惩罚的任务安排问题可描述如下。
     * (1）给定n个任务的集合S={1,2,…,n} ;
     * (2〉完成任务i需要t;时间，1≤i≤n;
     * (3）任务i的截止时间d;，1≤i≤n，即要求任务à在时间d;之前结束;
     * (4)任务i的误时惩罚w;，l≤i≤n，即任务i未在时间d;之前结束将招致w;的惩罚;若按时完成则无惩罚。
     * 任务安排问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。
     * ★算法设计:对于给定的n个任务，计算总误时惩罚最小的最优时间表。
     * ★数据输入:由文件input, txt给出输入数据。第1行是1个正整数n，表示任务数。接下来的n行中，每行有3个正整数a,b,c，表示完成相应任务需要时间a，截止时间为b，误时惩罚为c。
     * ★结果输出:将计算出的总误时惩罚输出到文件output.txt。
     */
    static class task {
        int t;//任务时间
        int d;//截止时间
        int w;//惩罚时间
    }

    private static final task[] a = new task[100];
    private static int bestw;//存储最短的任务惩罚时间
    private static int w;//当前的任务惩罚时间
    private static int t;//当前所做任务总时间
    private static int n;

    static void backtrack(int i) {
        if (i > n) {//到达叶节点
            bestw = w;
            return;
        }
        /*约束条件：所做任务总时间是否<=当前任务截止时间，成立进入左子树*/
        if (t + a[i].t <= a[i].d) {
            t += a[i].t;//更新总时间
            backtrack(i + 1);
            t -= a[i].t;//回溯结束时时间要还原
        }
        /*限界函数：当前总惩罚是否<=bestw，成立进入右子树，否则剪枝*/
        if (w + a[i].w <= bestw) {
            w = w + a[i].w;
            backtrack(i + 1);
            w = w - a[i].w;
        }
    }

    public static void main(String[] args) {
        Scanner scanner;
        FileWriter writer = null;
        try {
            scanner = new Scanner(new File("src/com/atguigu/algorithm/dfs/非单位时间任务安排问题_input.txt"));
            n = scanner.nextInt();//输入任务个数
            w = 0;
            t = 0;
            bestw = 1000;
            //先将bestw设置为一个较大的值
            for (int i = 1; i <= n; ++i) {
                a[i] = new task();
                a[i].t = scanner.nextInt();
                a[i].d = scanner.nextInt();
                a[i].w = scanner.nextInt();
            }
            //scanner.nextInt() >> a[i].t >> a[i].d >> a[i].w;
            backtrack(1);
            System.out.println(bestw);

            writer = new FileWriter("src/com/atguigu/algorithm/dfs/非单位时间任务安排问题_output.txt");
            writer.write(String.valueOf(bestw));
            writer.flush();
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                if (writer != null)
                    writer.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}
